/**
 * @param {string} digits
 * @return {string[]}
 */
 var letterCombinations = function (digits) {
    const k = digits.length;
    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    if (!k) return [];
    if (k === 1) return map[digits].split('')

    // 开始回溯
    const res = [],
        path = []
    dfs(digits, k, 0)
    return res

    function dfs(n, k, index) {
        if (path.length === k) {
            res.push(path.join(''))
            return
        }
        // 取数字对应的字符集
        for (const v of map[n[index]]) {
            path.push(v);
            dfs(n, k, index + 1);
            path.pop();
        }
    }
};